import javax.swing.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
class Solution {

    static class ListNode{
        int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public void create(){
        ListNode node1=new ListNode(4);
        ListNode node2=new ListNode(2);
        ListNode node3=new ListNode(1);
        ListNode node4=new ListNode(3);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        head=node1;
    }
    ListNode head;
    ListNode minNode ;
    public ListNode insertionSortList(ListNode head) {
        minNode= head;
        if(head==null) return null;
        insert(head,null);
        return minNode;
    }
    public ListNode insert(ListNode head,ListNode cur){
        ListNode node=null;
         if(head==null) return null;
        while(head!=null){
            if(cur==null||head.val>=cur.val){
                node = insert(head.next,head);
            }else{
                if(head.val<cur.val)
                return head;
            }
            if(node!=null&&node.val<head.val){
                if(node!=null&&node.val<minNode.val) minNode=node;
                head.next=node.next;
                if(cur!=null) cur.next=node;
                node.next=head;
                head=node;
            }
            if(node!=null&&cur!=null&&node.val<cur.val){
                // if(cur.val<minNode.val) minNode=cur;
                return node;
            }
            if(node==null) return null;
        }
        return minNode;
    }
//非递归
    public ListNode insertionSortList2(ListNode head){
        if(head==null) return null;
        ListNode dummyHead = new ListNode();
        dummyHead.next=head;
        ListNode lastNode = head;
        ListNode curr=head.next;
        while(curr!=null){
            if(curr.val<lastNode.val){
                for(ListNode pre=dummyHead;pre!=null;pre=pre.next){
                    if(pre.val<=curr.val&&pre.next.val>curr.val){
                        lastNode.next=curr.next;
                        curr.next=pre.next;
                        pre.next=curr;
                        if(pre==dummyHead) dummyHead.next=curr;
                        break;
                    }
                }
            }else{
                lastNode=curr;
            }
            curr=lastNode.next;
        }
        return dummyHead.next;
    }

}
//----------------------------------------------------------------
public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.create();
//        solution.insertionSortList(solution.head);
        solution.insertionSortList2(solution.head);
    }

    public static void main1(String[] args) {
        int[][] nums= {{1,3},{0,0},{3,5},{2,6},{1,3}};
//        int start=1;
//        int end=2;
//        int[] arr = {start,end};
//        for (int e:arr){
//            System.out.println(e);
//        }
//        int[][] num=new int[1][];
//        num[0]= new int[]{start, end};
//        for(int[] e:num){
//            for (int e1:e){
//                System.out.print(e1+" ");
//            }
//        }
//        HashSet<Integer[]> set = new HashSet<>();
//        System.out.println(Arrays.toString(nums));
//        for(Integer[] num:nums){
//            set.add(num);
//        }
//        System.out.println(set.toArray());
//        Arrays.
//        System.out.println(nums);
//        System.out.println(nums.length);
//        System.out.println(nums[0].length);

//        Main main = new Main();
//        main.merge(nums);
//        for(int[] e1:nums){
//            for(int e2:e1){
//                System.out.print(e2+" ");
//            }
//        }
//        int[][] arr=main.removeOverlap(nums);
//        for(int[] e1:arr){
//            for (int i:e1) {
//                System.out.println(i);
//            }
//        }
    }

//    public int[][] merge(int[][] intervals) {
//        bubbleSort(intervals);
//
//        return intervals;
//    }
//
//    public  void bubbleSort(int[][] array){
//        for (int i = 0; i < array.length-1; i++) {
//            boolean flag = false;
//            for (int j = 0; j < array.length-1-i; j++) {
//                if(array[j][0]>array[j+1][0]){
//                    swap(array,j+1,j);
//                    flag=true;
//                }
//            }
//            if(!flag) return ;
//        }
//    }
//    private void swap(int[][] array,int index1,int index2){
//        int[] tmp=array[index1];
//        array[index1]=array[index2];
//        array[index2]=tmp;
//    }
//    public int[][] removeOverlap(int[][] array){
//        List<int[]> list = new ArrayList<>();
//        for (int i = 0; i < array.length; i++) {
//            int l=array[i][0],r=array[i][1];
//            if(list.size()==0||list.get(list.size()-1)[1]<l){
//                list.add(new int[]{l,r});
//            }else{
//                if(list.get(list.size()-1)[1]>=l){
//                    int[] l1=list.get(list.size()-1);
//                    r=Math.max(l1[1],r);
//                    if(l1[1]<r){
//                        list.remove(list.size()-1);
//                        list.add(new int[]{l1[0],r});
//                    }
//                    }
//                }
//            }
//        return list.toArray(new int[list.size()][]);
//
//}
//
}